leetcode 全 O(1) 的数据结构

全 O(1) 的数据结构

请你实现一个数据结构支持以下操作：

• Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
• Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
• GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串”” 。
• GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串””。

挑战：

你能够以 O(1) 的时间复杂度实现所有操作吗？

---

• 来源：力扣（LeetCode）
• 链接：https://leetcode-cn.com/problems/all-oone-data-structure

代码：

19 89

class AllOne {

    //哈希表
    HashMap<String,Node> map=new HashMap<>();
    //链表
    //LinkedList<Node> list=new LinkedList<>();
    //节点头，节点尾
    Node head=new Node(-1,null);
    Node tail=new Node(-9,null);
    class Node{
        public int v;
        public HashSet<String> set=new HashSet<>();
        public Node pre=null;
        public Node next=null;
        Node(int vl,String str)
        {
            v=vl;
            if(str!=null)
                set.add(str);
        }
    };
    /** Initialize your data structure here. */
    public AllOne() {
        head.next=tail;
        head.pre=tail;
        tail.next=head;
        tail.pre=head;
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if(map.containsKey(key))
        {
            //如果已经含有这个key了，就更新这个节点
            Node temp=map.get(key);
            Node pre=temp.pre;
            if(pre.v-temp.v==1)
            {
                //如果前面那个节点刚好可以凑过去,就增加那个节点的值，并且判断节点是否移动
                temp.set.remove(key);
                pre.set.add(key);
                map.put(key,pre);
            }else{
                temp.set.remove(key);
                //加一
                pre.next=new Node(temp.v+1,key);
                temp.pre=pre.next;
                pre.next.pre=pre;
                pre.next.next=temp;
                map.put(key,pre.next);
            }
            //删除temp
            if(temp.set.size()==0)
            {
                temp.pre.next=temp.next;
                temp.next.pre=temp.pre;
            }
        }else{
            //如果没有key的话，插入
            if(tail.pre==head)
            {
                //没有东西，空链表
                Node temp=new Node(1,key);
                //Node p=tail.pre;
                head.next=temp;
                temp.pre=head;
                temp.next=tail;
                tail.pre=temp;
                //讲map索引指向这个节点
                map.put(key,temp);
            }
            else{
                if(tail.pre.v==1) {
                    //如果有点可以合并，首先考虑合并
                    Node p=tail.pre;
                    p.set.add(key);
                    //将hash表索引指向这个节点
                    map.put(key,p);
                }else{
                    //没有点可以合并，就不考虑合并了，直接创建这个点
                    Node temp=new Node(1,key);
                    Node p=tail.pre;
                    p.next=temp;
                    temp.pre=p;
                    temp.next=tail;
                    tail.pre=temp;
                    //讲map索引指向这个节点
                    map.put(key,temp);
                }
            }
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if(map.containsKey(key))
        {
            //如果已经含有这个key了，就更新这个节点
            Node temp=map.get(key);
            Node next=temp.next;
            if(temp.v==1)
            {
                temp.set.remove(key);
                map.remove(key);
            }
            else if(temp.v-next.v==1) {
                temp.set.remove(key);
                next.set.add(key);

                map.put(key,next);

            }else {
                temp.set.remove(key);
                //减1
                Node x=new Node(temp.v-1,key);
                next.pre=x;
                temp.next=x;
                x.next=next;
                x.pre=temp;

                map.put(key,x);
            }
            //删除temp
            if(temp.set.size()==0)
            {
                temp.pre.next=temp.next;
                temp.next.pre=temp.pre;
            }
        }else{
            //如果不含key，不操作
        }
    }

    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        if(head.next==tail)
        {
            return "";
        }
        else{
            return head.next.set.iterator().next();
        }
        //LinkedHashMap
    }

    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        if(tail.pre==head)
        {
            return "";
        }
        else{
            return tail.pre.set.iterator().next();
        }
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */